洛谷 P1026 统计单词个数 题解

发表于 | 分类于 | | 热度: ℃

Description

给出一个由小写字母组成的字符串（$p$ 行，每行 $20$ 个字母)，以及 $s$ 个单词。将此字母串分成 $k$ 份，使每份中包含的单词数之和最大（单词可以重叠，但其首字母不能重复使用）。

数据范围：$p<=10, 1<k<=40, 1<=s<=6$

Solution

设 $f[i][j]$ 为前 $i$ 个字符分成 $j$ 段的最大单词数；$cnt[i][j]$ 表示在 不考虑断开 的前提下 $[i,j]$ 区间的单词数。

首先预处理处 $cnt$ 数组。

转移方程：$f[i][j]=max(f[k][j-1]+cnt[k+1][i])$ （$k$ 为枚举上次断开的位置）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

string str, s = "", w[10];
int p, q, n, f[300][50], cnt[300][300];

bool get(int x, int y)
{
    for(int i = 0; i < w[y].size(); i++)
        if(s[i + x] != w[y][i]) return false;
    return true;
}

void solve()
{
    for(int i = 0; i < s.size(); i++)
        for(int j = i; j < s.size(); j++)
            for(int k = i; k <= j; k++)
                for(int h = 1; h <= n; h++)
                    if(k + w[h].size() - 1 <= j && get(k, h))
                    {
                        cnt[i][j]++;
                        break;
                    }
}

int main()
{
    scanf("%d%d", &p, &q);
    for(int i = 1; i <= p; i++)
    {
        cin >> str;
        s += str;
    }
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) cin >> w[i];
    memset(cnt, 0, sizeof(cnt));
    solve();
    memset(f, 0, sizeof(f));
    for(int i = 0; i < s.size(); i++)
        for(int j = 1; j <= min(i + 1, q); j++)
            for(int k = j - 2; k < i; k++)
                f[i][j] = max(f[i][j], f[k][j - 1] + cnt[k + 1][i]);
    printf("%d", f[s.size() - 1][q]);
    return 0;
}